Optimized Link State Routing

Optimized Link State Routing, kurz OLSR, ist ein Routingprotokoll für mobile Ad-hoc-Netze, das eine an die Anforderungen eines mobilen drahtlosen LANs angepasste Version des Link State Routing darstellt. Das Protokoll wird im RFC 3626 beschrieben.

Bei diesem verteilten und flexiblen Routingverfahren ist allen Knoten (Routern) die Netztopologie bekannt, sodass sie von Fall zu Fall den kürzesten Weg zum Ziel festlegen können. Als proaktives Routingprotokoll hält es die dafür benötigten Informationen jederzeit bereit. Zusätzliche Verbindungen können der Redundanz dienen. Insbesondere bei dichten Netzwerken kann durch OLSR die Performance verbessert werden.

Implementiert wird das Protokoll in olsrd.

Angewendet wird OLSR, neben anderen Protokollen, in Freifunk-Netzen und der Forschung.

Übersicht

Ein am Netz teilnehmendes Gerät (Knoten) sucht sich andere, sich in Reichweite befindlichen Knoten, so genannte Multipoint-Relays (MPR) aus, über die anschließend Nachrichten weitergeleitet werden. Bedingung für die Wahl als MPR ist eine bidirektionale Verbindung. Die Wahl an MPRs wird den anderen Knoten bekannt gegeben, wodurch Nachrichten nicht an alle Knoten in Reichweite übertragen werden. Durch die proaktive Verteilung der Routen-Informationen kann sich jeder Node jederzeit den kürzesten Weg zwischen zwei Punkten berechnen. Zusätzlich vorhandene Informationen zur Topologie können zu Redundanzwecken zwischen den Knoten geteilt werden. Das Protokoll arbeitet komplett dezentral, und auch eine sichere Übermittlung von Control-Messages ist nicht notwendig, da jeder Knoten periodisch seine Informationen weitergibt und so der Verlust einzelner Nachrichten verkraftet werden kann. Das Ziel der MPRs ist die Reduktion redundanter Nachrichten. Mit welchen anderen Protokollen OLSR kombiniert wird, ist nicht festgelegt.

Arbeitsweise

Die Topologieentdeckung erfolgt bei OLSR über zwei Arten von Nachrichten: HELLO- und Topology-Control (TC)-Nachrichten. HELLO-Nachrichten dienen zum Link Sensing, zur Nachbarentdeckung und zur Mitteilung der Multipoint-Relay-Wahl. Die TC-Nachrichten dienen dazu, die so gewonnenen Informationen über mögliche Verbindungen im Netz zu verteilen.

Ein im Netz teilnehmendes Gerät entdeckt seine 1-Hop- und 2-Hop-Nachbarn über die periodisch verschickten HELLO-Nachrichten. Diese enthalten die Adressen der bereits bekannten 1-Hop-Nachbarn sowie den Status der Verbindung zu ihnen und werden nicht weitergeleitet. Aus seinen 1-Hop-Nachbarn wählt jeder Knoten Multipoint Relays (MPRs), sodass er über sie jeden seiner 2-Hop-Nachbarn erreichen kann. Die MPRs sind die Knoten, die Broadcast-Nachrichten weiterleiten, was das Fluten effizienter macht. Sie sind es auch, die die TC-Nachrichten erstellen, die eine Liste mindestens der Knoten enthalten, von denen sie als MPRs gewählt wurden, sodass für jeden Knoten mindestens eine Möglichkeit bekannt ist, wie er erreicht werden kann. Diese TC-Nachrichten werden im gesamten Netzwerk verteilt. Auf diese Weise erhält jeder Knoten eine Vorstellung des Netzwerkes und kann Routingtabellen erstellen.

Nachfolger OLSRv2

Die Weiterentwicklung OLSRv2 ist im RFC 7181 beschrieben, dieses verweist auf vier vorausgegangene RFCs, welche speziell für OLSRv2 geschrieben wurden, und erweitert diese:

• RFC 6130 – Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP). April 2011 (aktualisiert durch RFC 7466, März 2011, englisch).
• RFC 5444 – Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format. Februar 2009 (aktualisiert durch RFC 8245, Oktober 2017, englisch).
• RFC 5497 – Representing Multi-Value Time in Mobile Ad Hoc Networks (MANETs) – definiert TLVs (type-length-value structure). März 2009 (englisch).
• RFC 5148 – Jitter. Februar 2008 (englisch).

Der Hauptunterschied zu OLSRv1 ist die aussagekräftigere Link-Metrik statt dem reinen Hop Count.

Implementiert wird das Protokoll von olsrd2.

Andere Ad-hoc-Routingprotokolle

• AODV
• B.A.T.M.A.N. – Weiterentwicklung von OLSRv1. Hier kennt nicht jeder Router das gesamte Netz.

Weblinks

• T. Clausen, P. Jacquet: RFC 3626 – Optimized Link State Routing Protocol (OLSR). Oktober 2003 (englisch).
• Implementation für Linux, FreeBSD, Windows und Mac OS: www.olsr.org (offizielle Homepage des OLSRd) und olsr.org Mailingliste
• Online Simulation einiger Routing Protokolle. (Java-Applet) dpunkt.de/mobile
• Praktische Anwendung in freien Funknetzen: Funkfeuer.at
• An die RFC angelehnte, einfache Funktionsbeschreibung zu OLSR. freifunk.net
• Podcast – CRE016 Wireless Mesh Networking. cre.fm – Aufbau von freien, selbstroutenden Netzwerken mit OLSR